#include <iostream>  
#include <vector>  
using namespace std;  
  
// 定义一个函数，用于求解n皇后问题  
bool solveNQueens(vector<int>& cols, vector<vector<string>>& res, int row, int n) {  
    // 如果已经排完了n行，说明找到了一个解，将结果加入到结果集中  
    if (row == n) {  
        vector<string> board(n, string(n, '.'));  
        for (int i = 0; i < n; i++) {  
            board[i][cols[i]] = 'Q';  
        }  
        res.push_back(board);  
        return true;  
    }  
  
    // 枚举每一列，尝试放置皇后  
    for (int col = 0; col < n; col++) {  
        bool conflict = false;  
        for (int i = 0; i < row; i++) {  
            if (cols[i] == col || abs(row - i) == abs(col - cols[i])) {  
                conflict = true;  
                break;  
            }  
        }  
        if (!conflict) {  
            cols[row] = col;  
            if (solveNQueens(cols, res, row + 1, n)) {  
                return true;  
            }  
            cols[row] = -1; // 回溯，将当前列的皇后移除  
        }  
    }  
    return false;  
}  
  
// 主函数，用于求解n皇后问题，并输出所有解  
void solveNQueens(int n) {  
    vector<vector<string>> res;  
    vector<int> cols(n, -1); // 用于记录每一行皇后所在的列数，初始化为-1表示没有皇后  
    solveNQueens(cols, res, 0, n); // 从第0行开始求解n皇后问题  
    for (int i = 0; i < res.size(); i++) {  
        for (int j = 0; j < n; j++) {  
            cout << res[i][j] << endl; // 输出棋盘的每一行  
        }  
        cout << endl; // 输出换行符，以便于观察结果  
    }  
}